package com.note.feng.leetcode.algorithms.easy.four;

import lombok.val;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FourHundredNine {

    /**
     * 409 最长回文串
     * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
     *
     * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
     *
     * 示例 1:
     *
     * 输入:s = "abccccdd"
     * 输出:7
     * 解释:
     * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
     * 示例 2:
     *
     * 输入:s = "a"
     * 输入:1
     * 示例 3:
     *
     * 输入:s = "bb"
     * 输入: 2
     *
     * 提示:
     *
     * 1 <= s.length <= 2000
     * s 只能由小写和/或大写英文字母组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/longest-palindrome
     */
    /**
     * 解法：贪心
     * 先统计出每个字符出现的次数，然后根据次数计算最长回文串，
     * 1、若次数是偶数，都可以加入到回文串中；
     * 2、若次数是奇数，则可以加入次数减一个到回文串中；
     * 3、回文串长度为奇数时，中间的字符只出现一次，故若有次数是奇数时，回文串长度增加一
     * @param s
     * @return
     */
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        int res = 0;
        boolean flag = false;
        for (Character character : map.keySet()) {
            int value = map.get(character);
            if (!flag && value % 2 == 1) {
                res++;
                flag = true;
            }
            res += value % 2 == 0 ? value : value - 1;
        }
        return res;
    }
}
